Parsing systems enable programs to either recognize or transcribe patterns matching formal grammars. Today many parsing systems are written by hand while others are auto-generated. They are found in compilers, natural language processing, machine communication, protocols, computer security, and many other domains. In compilers, for instance, parsers are integral to many functions including versioning, ambiguity resolution, and error recovery, among other things.
More specifically, parsers can perform syntactic analysis to verify input syntax. A stream of characters is lexically analyzed to recognize a sequence of tokens such as keywords, operators, and identifiers, among others. Often, these tokens are employed to generate a parse tree or a more compact abstract syntax tree (AST) as a function of a programming language grammar. The tree can be employed as a basis for subsequent processing including semantic analysis, optimization, and code generation.
Typically, mutability is leveraged at least implicitly to optimize programs including parsing systems in terms of resource utilization and performance. Mutability is a property of a programmatic construct that refers to an ability to change or be changed. For example, a type is mutable if the value of an instance of that type is allowed to change. By contrast, immutability refers to an inability to change. Accordingly, if the value of an instance of a type is not allowed to change, then the type is immutable.
Resource utilization is optimized by simply modifying or updating current structures as needed as opposed to generating multiple copies. For instance, mutable structures are very seductive with respect to parsing, and more specifically parsing and an integrated development environment (IDE). By way of example, as a user enters code into an editor of an IDE, a parse tree or the like can be updated to include the additional code or alteration of current code. Stated differently, a single, updatable representation of the program is cached and/or persisted and synchronized with the most current program version.
As per performance optimization, at least one of two approaches is taken conventionally. First, algorithms are developed that perform synchronous processing faster (e.g., quick sort, bubble sort . . . ) with the implicit understanding that constructs are mutable. Once a good algorithm is established, programmatic statements and/or instructions are analyzed and hacked. In other words, there is a lot of lower level instruction alteration and/or bit twiddling.